package leetcode.a1220;

import java.util.Arrays;

/**
 * 475. 供暖器
 * 这题研究不明白，暂时学习下里面用到的二分查找
 *
 * @author wh
 * @date 2021-12-20
 */
public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int ans = 0;
        Arrays.sort(heaters);
        for (int house : houses) {
            int i = binarySearch(heaters, house);
            int j = i + 1;
            int leftDistance = i < 0 ? Integer.MAX_VALUE : house - heaters[i];
            int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
            int curDistance = Math.min(leftDistance, rightDistance);
            ans = Math.max(ans, curDistance);
        }
        return ans;
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // 如果都不比第一位数大，那么久没必要比较了
        if (nums[left] > target) {
            return -1;
        }
        while (left < right) {
            // 取中间值 +1的目的是为了防止不够/2
            int mid = (right - left + 1) / 2 + left;
            if (nums[mid] > target) {
                // 这里设置= mid -1是为了防止死循环,我一开始有点疑惑为什么直接设置-1 如果-1后,right=left怎么办，
                // 后来发现nums[mid] 如果等于target就会走到else 部分。而继续循环后left<right，每次right便会减一直到left>=right
                right = mid - 1;
            } else {
                // 这里囊括了小于和等于
                left = mid;
            }
        }
        return left;
    }


    public int binarySearch1(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[left] > target) {
            return -1;
        }
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            // 因为这里用的是值比对。所以列表无序的话不生效
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 如果是等于就会走到这里,然后直到right=left
                left = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().binarySearch1(new int[]{1, 2, 4, 3, 5, 6, 7}, 4));
        ;
    }
}
